/*
 * @lc app=leetcode.cn id=206 lang=swift
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

//输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL
public class ListNode {
    public var val:Int
    public var next:ListNode?
    public init(_ val:Int) {
        self.val = val
        self.next = nil
    }
}

class Solution206 {
    // 迭代法：只是修改指向即可（推荐）
    func reverseList(_ head: ListNode?) -> ListNode? {
        var pre: ListNode?
        var cur = head
        while cur != nil {
            let next = cur?.next
            cur?.next = pre
            pre = cur
            cur = next
        }
        return pre
    }
    // 递归法：也只是修改指向即可
    func reverseList2(_ head: ListNode?) -> ListNode? {
        guard let node = head else {
            return head
        }
        guard let _ = node.next else {
            return node
        }
        let ret = reverseList2(node.next)
        node.next?.next = node
        node.next = nil
        return ret
    }

    //创建链表
    static func test()  {
        var head:ListNode?
        var tail:ListNode?
        for i in 1...5 {
            let node = ListNode(i)
            if i == 1 {
                head = node
                tail = head
            }else {
                tail?.next = node
                node.next = nil
                tail = node
            }
        }
        let reversedNode =  Solution206().reverseList2(head)
        var temp = reversedNode
        while temp != nil {
            print(temp!.val)
            temp = temp?.next
        }
    }
}


